package Midium;

import java.util.ArrayList;
import java.util.List;

public class Solution54 {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        __spiralOrder(0, matrix, list);
        return list;
    }

    public void __spiralOrder(int start, int[][] matrix, List<Integer> list) {
        //四个点分别为(a1,b1),(a2,b2),(a3,b3),(a4,b4)
        int a1 = start, b1 = start;
        int a2 = start, b2 = matrix[0].length - start - 1;
        int a3 = matrix.length - start - 1, b3 = matrix[0].length - start - 1;
        int a4 = matrix.length - start - 1, b4 = start;
        //递归终止
        if (a1 > a4 || b1 > b2)
            return;
        if (a1 == a4) {
            //把最后一行放进去
            for (int i = b1; i <= b2; i++) {
                list.add(matrix[a1][i]);
            }
            return;
        }
        if (b1 == b2){
            //把最后一列放进去
            for(int i = a1; i <= a4 ; i++){
                list.add(matrix[i][b1]);
            }
            return;
        }
        for (int i = b1; i < b2; i++) {
            list.add(matrix[a1][i]);
        }
        for (int i = a2; i < a3; i++) {
            list.add(matrix[i][b2]);
        }
        for (int i = b3; i > b4; i--) {
            list.add(matrix[a3][i]);
        }
        for (int i = a4; i > a1; i--) {
            list.add(matrix[i][b4]);
        }
        __spiralOrder(++start, matrix, list);
    }

    public static void main(String[] args) {
        Solution54 s = new Solution54();
        s.spiralOrder(new int[][]{{1,11},{2,12},{3,13},{4,14},{5,15}});
    }
}
